/*
2246. 相邻字符不同的最长路径
https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/
困难 2024/11/15
*/

class Solution {
public:
vector<vector<int>>mp;
int ans=0;
int dfs(string &s,int fu)
{
    int maxlen=0;
    int len=0;
    for(int i : mp[fu])
    {
        len=dfs(s,i)+1;
        if(s[i]!=s[fu])
        {
            ans=max(ans,maxlen+len);
            maxlen=max(maxlen,len);
        }
    }
    return maxlen;
}
    int longestPath(vector<int>& parent, string s) {
        int n=parent.size();
        mp.resize(n);
        for(int i=1;i<n;i++)
            mp[parent[i]].push_back(i);
        dfs(s,0);
        return ans+1;
    }
};